package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-03 17:23
 **/
public class LeetCode1414 {

    public static void main(String[] args) {
        LeetCode1414 c = new LeetCode1414();
        System.out.println(c.findMinFibonacciNumbers(7));
    }

    public int findMinFibonacciNumbers(int k) {
        List<Integer> list = new ArrayList<>();
        int a = 1;
        int b = 2;
        int c = a + b;
        list.add(a);
        list.add(b);
        while (c <= k) {
            list.add(c);
            a = b;
            b = c;
            c = a + b;
        }
        int res = 0;
        int i = list.size() - 1;
        while (k != 0) {
            int num = list.get(i);
            if (num <= k) {
                k -= num;
                ++res;
            } else {
                --i;
            }
        }
        return res;
    }

}
